package q105_builderTree;

import CommonClass.Common.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    // 先设置一个全局的map，用来记录每一个节点的中序index
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);

    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int pre_l, int pre_r, int in_l, int in_r) {
        if (pre_r < pre_l) {
            return null;
        }
        // 先序遍历是按照 根 左 右 的方式进行排列的 所以pre数组的最左边就是根节点
        TreeNode root = new TreeNode(preorder[pre_l]);
        // 根节点在中序遍历中的index
        int root_index = indexMap.get(preorder[pre_l]);
        // 用这个index可以计算左子树有多少个节点
        int left_num = root_index - in_l;
        // 所以 (pre_l + 1, pre_l + left_num) 这一段就是在pre中的左子树 (in_l, root_index - 1)则就是在in中的左子树
        root.left = myBuildTree(preorder, inorder, pre_l + 1, pre_l + left_num, in_l, root_index - 1);
        // 剩下的排除掉就是右子树
        root.right = myBuildTree(preorder, inorder, pre_l + left_num + 1, pre_r, root_index + 1, in_r);
        return root;
    }
}
